package lec04.pm.gm.v2;

public class BiLinkedList {

	public Node get(int index) {
		if (index < 0 || index >= size)
			throw new IllegalArgumentException();
		if (index < size / 2) {
			Node node = head.next;
			for (int i = 0; i < index; i++)
				node = node.next;
			return node;
		} else {
			Node node = tail.prev;
			for (int i = 0; i <size-index-1; i++)
				node = node.prev;
			return node;
		}
	}

	Node head, tail;
	int size;

	public BiLinkedList() {
		head = new Node(-1);
		tail = new Node(-1);
		head.setNext(tail);
		tail.setPrev(head);
		size = 0;

	}

	static class Node {
		public Node(int elem) {
			this.elem = elem;
			next = prev = null;
		}

		public void setNext(Node next) {
			this.next = next;

		}

		public int getElem() {
			return elem;
		}

		public void setElem(int elem) {
			this.elem = elem;
		}

		public Node getNext() {
			return next;
		}

		int elem;
		Node next;
		Node prev;

		public Node getPrev() {
			return prev;
		}

		public void setPrev(Node prev) {
			this.prev = prev;
		}
	}

	public static void main(String[] args) {
		BiLinkedList list = new BiLinkedList();
		for (int i = 0; i < 10; i++) {
			Node node = new Node(i);
			if (i % 2 == 0)
				list.append(node);
			else
				list.prepend(node);
			System.out.println(list);

		}
		for(int i=0;i<10;i++)
			System.out.println(list.get(i).getElem());
		for (int i = 0; i < 10; i++) {
			if (i % 2 == 0)
				list.popFirst();
			else
				list.popLast();
			System.out.println(list);

		}
	}

	public boolean popLast() {
		if (isEmpty())
			return false;
		Node r = tail, q = tail.prev, p = q.prev;
		removeQ(p, q, r);
		return true;

	}
	/**
	 *  p->q->r=>p->r
	 * @param p
	 * @param q
	 * @param r
	 */
	private void removeQ(Node p, Node q, Node r) {
		p.next = r;
		r.prev = p;
		q.prev = null;
		q.next = null;
		--size;
	}

	public boolean popFirst() {
		if (isEmpty())
			return false;
		Node p = head, q = head.next, r = q.next;
		removeQ(p, q, r);
		return true;

	}

	public void append(Node node) {
		Node p = tail.prev, r = tail, q = node;
		insertQ(p, q, r);

	}
/**
 *  p->r => p->q->r
 * @param p
 * @param q
 * @param r
 */
	private void insertQ(Node p, Node q, Node r) {
		p.next = q;
		q.next = r;
		r.prev = q;
		q.prev = p;
		++size;
	}

	public void prepend(Node node) {
		Node p = head,  q = node,r = head.next;
		insertQ(p, q, r);

	}

	public boolean remove(Node node) {
		Node p = node.prev, q = node, r = node.next;
		removeQ(p, q, r);
		return true;
	}

	@Override
	public String toString() {
		if (isEmpty())
			return "[]";
		StringBuffer buffer = new StringBuffer("[");

		for (Node node = head.next; node != tail; node = node.next)
			buffer.append(node.getElem() + ",");
		buffer.deleteCharAt(buffer.length()-1);
		buffer.append(']');

		return buffer.toString();
	}

	public boolean isEmpty() {
		return size == 0;
	}
}
